"""
看评论，提示用3指针,还真想不到这种方法


1
2: [0]*2, [0]*3, [0]*5
3: [1]*2, [0]*3, [0]*5
4: [1]*2, [1]*3, [0]*5
5: [2]*2, [1]*3, [0]*5
6: [2]*2, [1]*3, [1]*5
8: [3]*2, [2]*3, [1]*5
"""


class Solution:
    def nthUglyNumber(self, n: int) -> int:
        index2 = 0
        index3 = 0
        index5 = 0

        res = [1]
        while len(res) != n:
            res2 = res[index2] * 2
            res3 = res[index3] * 3
            res5 = res[index5] * 5

            res.append(min(res2, res3, res5))

            if res[-1] == res2:
                index2 += 1
            if res[-1] == res3:
                index3 += 1
            if res[-1] == res5:
                index5 += 1

        return res[-1]


if __name__ == "__main__":
    print(Solution().nthUglyNumber(100))
